class P440 {
	public static void main(String[] args) {
		int[] values = new int[151];
		values[3] = 2;
		values[4] = 5;
		values[5] = 2;
		values[6] = 4;
		values[7] = 3;
		values[8] = 11;
		values[9] = 2;
		values[10] = 3;
		values[11] = 8;
		values[12] = 16;
		values[13] = 4;
		values[14] = 21;
		values[15] = 6;
		values[16] = 5;
		values[17] = 2;
		values[18] = 11;
		values[19] = 20;
		values[20] = 34;
		values[21] = 8;
		values[22] = 15;
		values[23] = 10;
		values[24] = 7;
		values[25] = 13;
		values[26] = 11;
		values[27] = 13;
		values[28] = 45;
		values[29] = 18;
		values[30] = 23;
		values[31] = 8;
		values[32] = 3;
		values[33] = 2;
		values[34] = 25;
		values[35] = 75;
		values[36] = 42;
		values[37] = 13;
		values[38] = 5;
		values[39] = 23;
		values[40] = 13;
		values[41] = 50;
		values[42] = 16;
		values[43] = 18;
		values[44] = 89;
		values[45] = 38;
		values[46] = 8;
		values[47] = 39;
		values[48] = 30;
		values[49] = 29;
		values[50] = 38;
		values[51] = 7;
		values[52] = 45;
		values[53] = 23;
		values[54] = 137;
		values[55] = 46;
		values[56] = 63;
		values[57] = 17;
		values[58] = 48;
		values[59] = 5;
		values[60] = 46;
		values[61] = 34;
		values[62] = 140;
		values[63] = 33;
		values[64] = 39;
		values[65] = 2;
		values[66] = 28;
		values[67] = 29;
		values[68] = 79;
		values[69] = 33;
		values[70] = 48;
		values[71] = 3;
		values[72] = 10;
		values[73] = 46;
		values[74] = 120;
		values[75] = 6;
		values[76] = 37;
		values[77] = 17;
		values[78] = 8;
		values[79] = 44;
		values[80] = 15;
		values[81] = 160;
		values[82] = 20;
		values[83] = 35;
		values[84] = 144;
		values[85] = 104;
		values[86] = 179;
		values[87] = 153;
		values[88] = 24;
		values[89] = 8;
		values[90] = 265;
		values[91] = 19;
		values[92] = 9;
		values[93] = 62;
		values[94] = 7;
		values[95] = 139;
		values[96] = 19;
		values[97] = 44;
		values[98] = 93;
		values[99] = 182;
		values[100] = 27;
		values[101] = 158;
		values[102] = 185;
		values[103] = 193;
		values[104] = 17;
		values[105] = 82;
		values[106] = 3;
		values[107] = 11;
		values[108] = 43;
		values[109] = 55;
		values[110] = 21;
		values[111] = 41;
		values[112] = 146;
		values[113] = 29;
		values[114] = 80;
		values[115] = 59;
		values[116] = 8;
		values[117] = 29;
		values[118] = 66;
		values[119] = 19;
		values[120] = 160;
		values[121] = 59;
		values[122] = 28;
		values[123] = 129;
		values[124] = 127;
		values[125] = 120;
		values[126] = 72;
		values[127] = 45;
		values[128] = 157;
		values[129] = 2;
		values[130] = 63;
		values[131] = 127;
		values[132] = 81;
		values[133] = 318;
		values[134] = 513;
		values[135] = 98;
		values[136] = 28;
		values[137] = 32;
		values[138] = 231;
		values[139] = 236;
		values[140] = 411;
		values[141] = 26;
		values[142] = 45;
		values[143] = 5;
		values[144] = 303;
		values[145] = 228;
		values[146] = 66;
		values[147] = 9;
		values[148] = 205;
		values[149] = 65;
		
		int x = Integer.parseInt(readLn());
		
		while (x != 0) {
			System.out.println(values[x]);
			x = Integer.parseInt(readLn());
		}
	}
	
	static String readLn() {
        String newLine = System.getProperty("line.separator");
        StringBuffer buffer = new StringBuffer();
        int car = -1;
        try {
            car = System.in.read();
            while ((car > 0) && (car != newLine.charAt(0))) {
                buffer.append((char)car);
                car = System.in.read();
            }
            if (car == newLine.charAt(0))
            System.in.skip(newLine.length() - 1);
        } catch (java.io.IOException e) { return (null);}
        if ((car < 0) && (buffer.length() == 0)) return (null);
        return (buffer.toString()).trim();
    }

}
